1. Field of the Invention
The present invention relates to compilers and techniques for improving computer system performance. More specifically, the present invention relates to a method and apparatus that facilitates method-level and/or loop-level value prediction in order to support speculative execution during space and time dimensional execution of a computer program.
2. Related Art
As increasing semiconductor integration densities allow more transistors to be integrated onto a microprocessor chip, computer designers are investigating different methods of using these transistors to increase computer system performance. Some recent computer architectures exploit “instruction level parallelism,” in which a single central processing unit (CPU) issues multiple instructions in a single cycle. Given proper compiler support, instruction level parallelism has proven effective at increasing computational performance across a wide range of computational tasks. However, inter-instruction dependencies generally limit the performance gains realized from using instruction level parallelism to a factor of two or three.
Another method for increasing computational speed is “speculative execution” in which a processor executes multiple branch paths simultaneously, or predicts a branch, so that the processor can continue executing without waiting for the result of the branch operation. By reducing dependencies on branch conditions, speculative execution can increase the total number of instructions issued.
Unfortunately, conventional speculative execution typically provides a limited performance improvement because only a small number of instructions can be speculatively executed. One reason for this limitation is that conventional speculative execution is typically performed at the basic block level, and basic blocks tend to include only a small number of instructions. Another reason is that conventional hardware structures used to perform speculative execution can only accommodate a small number of speculative instructions.
What is needed is a method and apparatus that facilitates speculative execution of program instructions at a higher level of granularity so that many more instructions can be speculatively executed.
One problem with speculative execution is that data dependencies can often limit the amount of speculative execution that is possible. For example, if a method returns a value that is used in subsequent computational operations, the value must be returned before the subsequent computational operations can proceed. Hence, the system cannot speculatively execute the subsequent computational operations until the method returns.
However, return values for methods and other collections of instructions are often predictable. For example, a method very frequently returns the same value or a predictable value during successive invocations of the method. Furthermore, even if a method return value is not predicted correctly, the method return value may not be used by subsequent program instructions. Hence, it may be possible to improve computer system performance by predicting a value produced by a section of program code in order to allow speculative execution to proceed.
Hence, what is needed is a method and an apparatus that facilitates predicting values generated by a section of program code in order to facilitate speculative program execution.
Note that people have suggested performing value prediction for a single computer instruction with long or unpredictable latency, such as a load operation or a square root operation. However, a predicted value generated for a single instruction cannot be used to facilitate performing speculative execution of program instructions at a higher level of granularity, for example predicting the outcome of a function.